import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-13
 * Time: 23:02
 */
class Solution {
    /**
     *  广度优先遍历
     */
    public boolean validPath1(int n, int[][] edges, int source, int destination) {
        List<Integer>[] lists = new List[n];
        for (int i = 0; i < n; i++) {
            lists[i] = new ArrayList<Integer>();
        }
        // 记录每个位置的邻接节点
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            lists[x].add(y);
            lists[y].add(x);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(source);
        visited[source] = true;
        while (!queue.isEmpty()) {
            int src = queue.poll();
            if (src == destination) {
                break;
            }
            for (Integer pos: lists[src]) {
                if (!visited[pos]) {
                    // 没有被遍历过
                    queue.offer(pos);
                    visited[pos] = true;
                }
            }
        }
        return visited[destination];
    }


    /**
     *  使用并查集
     */
    public boolean validPath2(int n, int[][] edges, int source, int destination) {
        int[] ufs = new int[n];
        Arrays.fill(ufs, -1);
        int edgeCount = edges.length;
        for (int i = 0; i < edgeCount; i++) {
            int src = edges[i][0];
            int dest = edges[i][1];
            // 进行合并
            // 先 ++
            // 再添加进去
            int root1 = findRoot(ufs, src);
            int root2 = findRoot(ufs, dest);
            if (root1 != root2) {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }
        // 判断两个节点是否在同一个集合中
        return findRoot(ufs, source) == findRoot(ufs, destination);
    }

    /**
     *  查找根
     */
    public int findRoot(int[] ufs, int pos) {
        while (ufs[pos] >= 0) {
            pos = ufs[pos];
        }
        return pos;
    }
}